#include<stdio.h>
#include<stdbool.h>
#include"Stack.h"





void PreOrder1(BiTree T)
{
	if (T != NULL)
	{
		printf("%d ", T->data);
		PreOrder1(T->lchild);
		PreOrder1(T->rchild);
	}
}

void EnOrder1(BiTree T)
{
	if (T != NULL)
	{
		EnOrder1(T->lchild);
		printf("%d ", T->data);
		EnOrder1(T->rchild);
	}
}

void PostOrder1(BiTree T)
{
	if (T != NULL)
	{
		PostOrder1(T->lchild);
		PostOrder1(T->rchild);
		printf("%d ", T->data);
	}
}

void PreOrder2(BiTree T)
{
	BiTnode* p = T;
	Stack s;
	Init(&s);
	while (p != NULL || IsEmpty_S(&s) != true)
	{
		if (p != NULL)
		{
			Push(&s, p);
			printf("%d ", p->data);
			p = p->lchild;
		}
		else
		{
			p = GetTop(&s);
			Pop(&s);
			p = p->rchild;
		}
	}
}

void EnOrder2(BiTree T)
{
	BiTnode* p = T;
	Stack s;
	Init(&s);
	while (p != NULL || IsEmpty_S(&s) != true)
	{
		if (p != NULL)
		{
			Push(&s, p);
			p = p->lchild;
		}
		else
		{
			p = GetTop(&s);
			printf("%d ", p->data);
			Pop(&s);
			p = p->rchild;
		}
	}
}

void LevelOrder(BiTree T)
{
	Queue q;
	Init_Queue(&q);
	BiTnode* p = T;
	EnOrder(&q,p);
	while (IsEmpty_Q(&q)!=true)
	{
		DeOrder(&q,&p);
		printf("%d ", p->data);
		if (p->lchild != NULL)
			EnOrder(&q, p->lchild);
		if (p->rchild != NULL)
			EnOrder(&q, p->rchild);
	}
}


int main()
{
	BiTnode b1, b2, b3, b4, b5,b6;
	b1.data = 1, b2.data = 2, b3.data = 3, b4.data = 4, b5.data = 5,b6.data=6;
	b1.lchild = &b2 ,  b1.rchild = &b3;
	b2.lchild = NULL, b2.rchild = &b4, b4.lchild = &b6, b4.rchild = NULL;
	b3.lchild = NULL, b3.rchild = &b5;
	b6.lchild = b6.rchild = b5.lchild = b5.rchild = NULL;
	//PreOrder2(&b1);
	//printf("\n");
	//EnOrder2(&b1);
	//printf("\n");
	//PostOrder(&b1);
	//printf("\n");
	LevelOrder(&b1);

	return 0;
}